package L7.L713;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * todo
 *
 * @author: luolidong
 * @create: 2021-07-13 11:12
 * @version: 1.0
 */
public class Demo2 {
    public boolean wordBreak(String s, List<String> wordDict) {
        Map<String,Boolean> map=new HashMap<>();
        for(String s1:wordDict){
            map.put(s1, true);
        }
        //dp[i] 代表索引i位置是否可以拆分
        boolean[] dp=new boolean[s.length()+1];
        dp[0]=true;
        for (int i = 1; i <=s.length() ; i++) {
            for (int j = i-1; j >=0 ; j--) {
                dp[i]=dp[j]&&(map.get(s.substring(j, i)) != null);
                if(dp[i]) break;
            }
        }
        return dp[s.length()];
    }

    public static void main(String[] args) {
    }
}
